package LeetCode.month02.day50;

public class No138 {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        for(Node node = head;node!=null;node = node.next.next){
            Node NewNode = new Node(node.val);
            NewNode.next = node.next;
            node.next = NewNode;
        }
        for(Node node = head; node!=null; node = node.next.next){
            Node node1 = node.next;
            node1.random = node.random==null? null:node.random.next;
        }
        Node newhead = head.next;
        for (Node node = head;node!=null;node=node.next){
            Node node1 = node.next;
            node.next = node1.next;
            node1.next = node1.next==null?null:node1.next.next;
        }
        return newhead;
    }
}
